package leetcode.problems;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by gmwang on 2018/7/25
 * 传统排序字符串
 */
public class _0827FindAllDuplicatesInAnArray {
    /**
     *
     * Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
     * 给定一个整数数组，1 ≤ a[i] ≤ n （n＝数组大小），一些元素出现两次，另一个出现一次。
     * Find all the elements that appear twice in this array.
     * 找到在数组中出现两次的所有元素。
     * Could you do it without extra space and in O(n) runtime?
     *
     * Example:
     * Input:
     * [4,3,2,7,8,2,3,1]
     *
     * Output:
     * [2,3]
     /**
     *
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List list = new ArrayList<>();
        if (nums.length == 0) return list;
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) != null && (int)map.get(nums[i]) == 1) list.add(nums[i]);
            else map.put(nums[i],map.getOrDefault(nums[i],1));
        }
        return list;
    }
//    public List<Integer> findDuplicates(int[] arr) {
//        int i;
//        List<Integer> res = new ArrayList<Integer>();
//        for (i = 0; i < arr.length; i++)
//        {
//            if (arr[Math.abs(arr[i])-1] >= 0)
//                arr[Math.abs(arr[i])-1] = -arr[Math.abs(arr[i])-1];
//            else
//                res.add(Math.abs(arr[i]));
//        }
//        return res;
//    }
    @Test
    public void test() {
        int[] nums = {4,3,2,7,8,2,3,1};
        List res = findDuplicates(nums);
        System.out.println(res);
    }
}
